ในด้านทฤษฎีกราฟ เรื่อง ต้นไม้ คือการแทนความเป็นระเบียบในเชิงสถาปัตยกรรม ต่างจากเครือข่ายที่วุ่นวายที่อาจมีเส้นทางหลายเส้นทางไปยังจุดหมายเดียวกัน แต่ต้นไม้จะให้เส้นทางเดียวและเฉพาะเจาะจงระหว่างจุดใดๆ ข้อจำกัดเชิงโครงสร้างนี้ไม่ใช่ข้อจำกัด แต่เป็นรากฐานสำคัญของระบบแบบลำดับชั้น ตั้งแต่ต้นตอสายสกุลเทพกรีก จนถึงโครงสร้างไดเรกทอรีในระบบปฏิบัติการสมัยใหม่
1. กายวิภาคของต้นไม้
ก่อนที่ลำดับชั้นจะปรากฏ เราจะมี ต้นไม้เสรี. นิยามของมันงดงามด้วยความเรียบง่าย:
นิยาม 9.1.1
ต้นไม้ (เสรี) $T$ คือกราฟแบบง่ายที่สำหรับจุดยอดสองจุดใดๆ $v$ และ $w$ จะมีเส้นทางง่ายที่ไม่ซ้ำกันเพียงเส้นเดียวจาก $v$ ไปยัง $w$ เส้นทางง่ายที่ไม่ซ้ำกัน จาก $v$ ไปยัง $w$ ซึ่งหมายความว่า กราฟนี้มีลักษณะทั้ง ต่อเนื่อง และ ไม่มีวงจร (ไม่มีวงจร)
เมื่อเราเลือกจุดยอดเฉพาะหนึ่งเป็น "จุดกำเนิด" เราจะสร้าง ต้นไม้ที่มีราก. การเปลี่ยนแปลงนี้ทำให้เกิดทิศทางเชิงพื้นที่ ซึ่งความสัมพันธ์จะถูกกำหนดโดยระยะห่างและความทิศทางจากจุดราก
คำศัพท์ลำดับชั้น
ในต้นไม้ที่มีจุดราก $v_0$ พิจารณาเส้นทางง่าย $(v_0, v_1, \dots, v_n)$:
- ผู้ปกครอง: จุดยอด $v_{n-1}$ เป็นผู้ปกครองของ $v_n$
- ลูกหลาน: $v_n$ เป็นลูกหลานของ $v_{n-1}$
- พี่น้อง: จุดยอดที่มีผู้ปกครองร่วมกัน
- บรรพบุรุษ: จุดยอดทั้งหมดบนเส้นทางจากจุดรากไปยัง $v_n$ (ยกเว้นตัวเองในบางบริบท)
- ลูกหลาน: จุดยอดทั้งหมดที่มี $v$ เป็นบรรพบุรุษ
มาตรการเชิงโครงสร้าง
- ระดับ: ความยาวของเส้นทางเดียวจากจุดรากไปยังจุดยอด จุดรากอยู่ที่ ระดับ 0.
- ความสูง: จำนวนระดับสูงสุดที่มีอยู่ในต้นไม้
- ใบ (จุดปลาย): จุดยอดที่ไม่มีลูกหลาน คือจุดสิ้นสุดของกิ่งสาขา
- จุดยอดภายใน (กิ่ง): จุดยอดที่มีลูกหลานอย่างน้อยหนึ่งคน
🎯 แนวคิดหลัก: ต้นไม้ย่อย
ต้นไม้ย่อย คือชุดย่อยของต้นไม้ที่ประกอบด้วยจุดยอดหนึ่งจุดและลูกหลานทั้งหมดของจุดนั้น ในระบบไฟล์ นี่คือโฟลเดอร์และไฟล์/โฟลเดอร์ย่อยทุกไฟล์ที่อยู่ภายใน มีตัวอย่างในรูปที่ 9.2.1 สายเลือดของ is a subset of a tree consisting of a vertex and all its descendants. In a file system, this is a folder and every file/subfolder inside it. In Figure 9.2.1, the lineage of โครนัส (เซียส พอสีโดน ฮาเดส อารีส) เป็นต้นไม้ย่อยของ อูราโนส.
2. การนำไปใช้ในโลกแห่งความเป็นจริง
ต้นไม้ไม่ใช่เพียงแค่แนวคิดทางคณิตศาสตร์ แต่เป็นโครงสร้างพื้นฐานของการจัดระเบียบ:
- ระบบแฟ้มคอมพิวเตอร์: 'C:' เป็นจุดราก โฟลเดอร์คือจุดยอดภายใน ไฟล์คือใบ
- แผนภูมิการบริหาร: ซีอีโอคือจุดราก ผู้จัดการคือจุดยอดภายใน ผู้มีส่วนร่วมแต่ละคนคือใบ
- กรอบการตัดสินใจ: แก้ปริศนาเช่น อินสแตนต์ อินซานิตี้ หรือการวิเคราะห์ ความแบนของน-คิวบ์ มักเกี่ยวข้องกับการสำรวจพื้นที่สถานะที่คล้ายต้นไม้